package 笔试;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class 查找二叉搜索树的叶子节点 {
    private static List<Integer> res;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String[] str = s.split(" ");
        int n = str.length;
        int[] nums = new int[n];
        res = new ArrayList<>();

        for(int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(str[i]);
        }

        dfs(nums, 0, n-1);
        for(int r : res) {
            System.out.print(r + " ");
        }
    }

    private static void dfs(int[] nums, int left, int right) {
        if(left == right) {
            res.add(nums[left]);
            return;
        } else if(left > right) {
            return;
        }
        int root = nums[left];
        // 找到右子树的起点
        int rightStart = left + 1;
        for(int i = left + 1; i <= right; i++) {
            if(nums[i] > root) {
                rightStart = i;
                break;
            }
        }
        if(nums[rightStart] > root) {
            dfs(nums, left+1, rightStart-1);
            dfs(nums, rightStart, right);
        } else {
            dfs(nums, left+1, right);
        }
    }
}
